/*
 * @Author: szx
 * @Date: 2022-01-12 14:09:36
 * @LastEditTime: 2022-01-12 14:23:43
 * @Description:
 * @FilePath: \leetcode\400-499\416\416.js
 */
/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canPartition = function (nums) {
    const sum = nums.reduce((prev, curr) => prev + curr);
    if (sum & 1) return false;
    const target = Math.floor(sum / 2);
    const dp = new Array(target + 1).fill(0);

    for (let i = 0; i < nums.length; i++) {
        for (let j = target; j >= nums[i]; j--) {
            dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
        }
    }
    return dp[target] == target;
};
